
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2423. -- [HAOI2010]最长公共子序列 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2423: [HAOI2010]最长公共子序列</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>128 MB<br><span class=green>Submit: </span>163&nbsp;&nbsp;<span class=green>Solved: </span>42<br>[<a href='submitpage.php?id=2423'>Submit</a>][<a href='problemstatus.php?id=2423'>Status</a>][<a href='bbs.php?id=2423'>Discuss</a>]</center><h2>Description</h2><div class=content><p class="MsoNormal" align="left" style="margin-top:12.0pt;margin-right:0cm;
margin-bottom:6.0pt;margin-left:0cm;text-align:left;line-height:150%;
mso-pagination:widow-orphan;background:white;word-break:break-all"><font class="Apple-style-span" face="宋体" size="6"><span class="Apple-style-span" style="font-size: 19px; line-height: 28px;"><b><br />
</b></span></font></p>
<p class="MsoNormal" style="text-indent:21.0pt"><b style="mso-bidi-font-weight:
normal"><span style="font-size:12.0pt;font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列<span lang="EN-US">X=</span>&ldquo;<span lang="EN-US">x<sub>0</sub></span>，<span lang="EN-US">x<sub>1</sub></span>，&hellip;，<span lang="EN-US">x<sub>m<st1:chmetcnv unitname="&rdquo;" sourcevalue="1" hasspace="False" negative="True" numbertype="1" tcsc="0" w:st="on">-1<span lang="EN-US" style="vertical-align:baseline"><span lang="EN-US">&rdquo;</span></span></st1:chmetcnv><span lang="EN-US" style="vertical-align:baseline">，序列Y=</span></sub></span>&ldquo;<span lang="EN-US">y<sub>0</sub></span>，<span lang="EN-US">y<sub>1</sub></span>，&hellip;，<span lang="EN-US">y<sub>k<st1:chmetcnv unitname="&rdquo;" sourcevalue="1" hasspace="False" negative="True" numbertype="1" tcsc="0" w:st="on">-1<span lang="EN-US" style="vertical-align:baseline"><span lang="EN-US">&rdquo;</span></span></st1:chmetcnv><span lang="EN-US" style="vertical-align:baseline">是X</span></sub></span>的子序列，存在<span lang="EN-US">X</span>的一个严格递增下标序列<span lang="EN-US">&lt;i<sub>0</sub></span>，<span lang="EN-US">i<sub>1</sub></span>，&hellip;，<span lang="EN-US">i<sub>k-1</sub>&gt;</span>，使得对所有的<span lang="EN-US">j=0</span>，<span lang="EN-US">1</span>，&hellip;，<span lang="EN-US">k-1</span>，有<span lang="EN-US">x<sub>ij</sub> = y<sub>j</sub></span>。例如，<span lang="EN-US">X=</span>&ldquo;<span lang="EN-US">ABCBDAB</span>&rdquo;，<span lang="EN-US">Y=</span>&ldquo;<span lang="EN-US">BCDB</span>&rdquo;是<span lang="EN-US">X</span>的一个子序列。<span lang="EN-US"><o:p></o:p></span></span></b></p>
<p class="MsoNormal" style="text-indent:21.0pt"><b style="mso-bidi-font-weight:
normal"><span style="font-size:12.0pt;font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。<span lang="EN-US"><o:p></o:p></span></span></b></p>
<p class="MsoBodyTextIndent" style="text-indent:0cm"><b style="mso-bidi-font-weight:
normal"><span lang="EN-US" style="font-size:12.0pt"><o:p>&nbsp;</o:p></span></b></p>
<p class="MsoBodyTextIndent" style="text-indent:0cm"><font class="Apple-style-span" size="4"><span class="Apple-style-span" style="font-size: 16px;"><b><br />
</b></span></font></p>
<p></p></div><h2>Input</h2><div class=content><div></div>
<div>
<p class="MsoNormal" style="text-indent: 21pt; "><b><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; "><o:p>&nbsp;</o:p></span></b></p>
<p class="MsoNormal" style="text-indent: 21pt; "><b><span style="font-size: 12pt; font-family: 宋体; ">第<span lang="EN-US">1</span>行为第<span lang="EN-US">1</span>个字符序列，都是大写字母组成，以</span></b><b><span lang="EN-US" style="font-size: 12pt; ">&rdquo;</span></b><b><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; ">.</span></b><b><span lang="EN-US" style="font-size: 12pt; ">&rdquo;</span></b><b><span style="font-size: 12pt; font-family: 宋体; ">结束。长度小于<span lang="EN-US">5000</span>。<span lang="EN-US"><o:p></o:p></span></span></b></p>
<p class="MsoNormal" style="text-indent: 21pt; "><b><span style="font-size: 12pt; font-family: 宋体; ">第<span lang="EN-US">2</span>行为第<span lang="EN-US">2</span>个字符序列，都是大写字母组成，以</span></b><b><span lang="EN-US" style="font-size: 12pt; ">&rdquo;</span></b><b><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; ">.</span></b><b><span lang="EN-US" style="font-size: 12pt; ">&rdquo;</span></b><b><span style="font-size: 12pt; font-family: 宋体; ">结束，长度小于<span lang="EN-US">5000</span>。<span lang="EN-US"><o:p></o:p></span></span></b></p>
<p class="MsoNormal" style="text-indent: 21pt; "><b><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; "><o:p>&nbsp;</o:p></span></b></p>
<p class="MsoBodyTextIndent" style="text-indent: 0cm; "><font class="Apple-style-span" size="4"><span class="Apple-style-span" style="font-size: 16px;"><b><br />
</b></span></font></p>
<p class="MsoBodyTextIndent" style="text-indent: 21pt; "></p>
</div>
<div>
<p></p>
</div></div><h2>Output</h2><div class=content><div></div>
<div>
<p class="MsoBodyTextIndent" style="text-indent: 21pt; "><b><span lang="EN-US" style="font-size: 12pt; "><o:p>&nbsp;</o:p></span></b></p>
<p class="MsoBodyTextIndent" style="text-indent: 21pt; "><b><span style="font-size: 12pt; ">第<span lang="EN-US">1</span>行输出上述两个最长公共子序列的长度。<span lang="EN-US"><o:p></o:p></span></span></b></p>
<p class="MsoBodyTextIndent" style="text-indent: 21pt; "><b><span style="font-size: 12pt; ">第<span lang="EN-US">2</span>行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对<span lang="EN-US">100,000,000</span>求余即可。<span lang="EN-US"><o:p></o:p></span></span></b></p>
<p class="MsoBodyTextIndent" style="text-indent: 21pt; "><font class="Apple-style-span" face="'Times New Roman'" size="4"><span class="Apple-style-span" style="font-size: 16px;"><b><br />
</b></span></font></p>
<p class="MsoBodyTextIndent" style="text-indent: 21pt; "></p>
</div>
<div>
<p></p>
</div></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>ABCBDAB.<br />
<br />
BACBBD.<br />
<br />
 <br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
<br />
4<br />
<br />
7</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day1'>Day1</a></p></div><center>[<a href='submitpage.php?id=2423'>Submit</a>][<a href='problemstatus.php?id=2423'>Status</a>][<a href='bbs.php?id=2423'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
